package l.l.w.leetcode.wordbreak;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * Created by llw on 2018/5/16/0016.
 */
public class Wordbreak {
    public boolean wordBreak(String s, Set<String> dict) {
        if(s == null || dict == null) return false;
        if(dict.contains(s)) return true;
        HashMap<String, Boolean> map = new HashMap<>();
        return wordBreak(s, dict, 0, s.length(),map);
    }

    private boolean wordBreak(String s, Set<String> dict,int start, int end,HashMap<String, Boolean> map){
        if(dict.contains(s.substring(start,end))) {
            map.put(s.substring(start,end),true);
            return true;
        }
        if(map.containsKey(s)){
            return map.get(s);
        }
        int len = s.length();
        for(int i = start + 1; i < end; ++i){
            boolean temp = wordBreak(s,dict, start,i,map);
            if(!temp) continue;
            temp = wordBreak(s, dict, i,end,map);
            if(temp) {
                map.put(s.substring(start,end),true);
                return true;
            }
        }
        map.put(s.substring(start,end),false);
        return false;
    }

    public static void main(String[] args) {
//        String s = "bccdbacdbdacddabbaaaadababadad";
//        String[] arr = {"cbc","bcda","adb","ddca","bad","bbb","dad","dac","ba","aa","bd","abab","bb","dbda","cb","caccc","d","dd","aadb","cc","b","bcc","bcd","cd","cbca","bbd","ddd","dabb","ab","acd","a","bbcc","cdcbd","cada","dbca","ac","abacd","cba","cdb","dbac","aada","cdcda","cdc","dbc","dbcb","bdb","ddbdd","cadaa","ddbc","babb"};
//        Set<String> set = new HashSet<>(Arrays.asList(arr));
            String s = "leetcode";
        Set<String> set = new HashSet<>();
        set.add("leet");
        set.add("code");
        boolean result = new Wordbreak().wordBreak(s, set);
        System.out.println(result);
    }
}
